package cn.zifangsky.tree.binarytree.questions;

import org.junit.Test;

import cn.zifangsky.tree.binarytree.BinaryTreeNode;

/**
 * 对于给定的两棵树，判断它们的结构是否相同？
 * @author zifangsky
 *
 */
public class Question10 {
	
	/**
	 * 对于给定的两棵树，判断它们的结构是否相同
	 * 
	 * @时间复杂度 O(n)
	 * @param root1 二叉树1的根节点
	 * @param root2 二叉树2的根节点
	 * @return
	 */
	public boolean checkSameTrees(BinaryTreeNode<Integer> root1,BinaryTreeNode<Integer> root2){
		if(root1 == null && root2 == null){
			return true;
		}
		
		if(root1 == null || root2 == null){
			return false;
		}
		
		return root1.getData().intValue() == root2.getData().intValue()
				&& checkSameTrees(root1.getLeft(), root2.getLeft())
				&& checkSameTrees(root1.getRight(), root2.getRight());
	}

	/**
	 * 测试用例
	 */
	@Test
	public void testMethods(){
		BinaryTreeNode<Integer> root1 = new BinaryTreeNode<>(1); //根节点1
		BinaryTreeNode<Integer> root2 = new BinaryTreeNode<>(1); //根节点2
		
		root1.setLeft(new BinaryTreeNode<>(2));root2.setLeft(new BinaryTreeNode<>(2));
//		root1.setRight(new BinaryTreeNode<>(3));
		
		System.out.println(checkSameTrees(root1,root2));
	}

}
